Generally speaking, there are two basic methods of time-multiplexing in broadband communications. The STM (synchronous transfer mode) assumes a common time reference called a frame reference among the terminals and each slot in a frame reference (or simply frame) is dedicated to the communication between two terminals. The ATM (asynchronous transfer mode), on the other hand, has no such common time reference. In one form of the ATM, each terminal transports fixed length blocks of information called cells (fixed length cells) or packets (fixed length packets). Each packet carries a data field and a header field (or simply header), the latter of which forms the preamble of a packet and contains source address, destination address, control bits etc.. More detailed discussion on broadband multiplexing and switching technologies are found in "Network, Transport, and Switching Integration for Broadband Communications" by J.Y. Hui, in IEEE Network, March 1989, pp 40-51.
The simplest structure of a switching node connecting m inlets and n outlets is an m.times.n matrix. An SDS (space division switch) is a matrix switch. When an SDS is used for interconnecting transmission links that are time multiplexed in an STM format, its cross-point setting is reconfigured for each time slot. The SDS is therefore considered as time multiplexed, hence the name Time Multiplexed Switch (TMS). A TMS can easily be viewed as many SDSs in parallel along the time axis. In circuit switching used for STM links, the matrix structure has been implemented in various ways to form a fully connected network which also alleviates time slot mismatch and output contention problem. Examples of the matrix-based architectures are the S-T-S (space-time-space), the T-S-T (time-space-time) and more recently the single-stage-equivalent structure described in U.S. Pat. No. 4,470,139, issued on Sept. 4, 1984 (Munter), where each cross point is a time switch, resulting in a strictly non-blocking node.
These matrix structures have been considered for packet switching for ATM networks. However, the same problem of output contention for TMS arises, that is to say, due to the absence of scheduling, more than one packet may compete for a given outlet during the same time slot (packet duration). Naturally, only one would be transmitted and the rest must stay in their queues and repeat the attempt during the subsequent time slots. There may be several inlet packets competing for a smaller number of outlets and the control mechanism must resolve the contention during each time slot, which may be of the order of a microsecond or so.
The time switch in the three stage T-S-T configuration used for STM networks cannot solve this problem for ATM networks for two reasons. First, ATM is inherently an FCFS (first come first serve) network without a frame reference. Hence a packet on an input ATM link would have to wait until the output is available. Consequently, an FCFS waiting room via buffering, instead of buffering for the time switch, is necessary at the inputs. Second, the destination addresses of packets on an ATM link may not have the periodic structure inherent in an STM network.
According to J.Y. Hui referenced above, two major switching methodologies are currently known for interconnecting large numbers of ATM links. The first approach alleviates output contention, or contention anywhere in a multi-stage connection network, by extensively using FCFS buffering at the internal links of the switching network. The interconnection network used is often a variation of the banyan network. Therefore, contention is localized to switch nodes with buffering to hold contending packets. The second approach avoids the use of internal buffering but employs sorting as a switching mechanism for computing cross-point setting and resolving output contention. The interconnection network used is a Batcher sorting network placed before a banyan-type network.
Various techniques addressing these and other problems concerning ATM and STM are found in the following laid-open Canadian Patent Applications: No. 2,003,259, opened on May 25, 1990 (Fukaya et al), mentions a broadband ATM ISDN digital exchange which uses a modified banyan network with an identification bit in the cell header to indicate whether effective data is stored; No. 2,006,102, opened on Jun. 24, 1990 (De Somer), shows a communication switching system for STM and ATM cell streams using a multiplexer which samples streams in predetermined order and at frequencies equal to the sum of time slot frequencies; and No. 2,006,392, opened on Jun. 23, 1990 (Lobjinski et al), teaches a single-stage digital coupling network using ATM which allows a modular expansion to have a coupling matrix with pre-connection and end connection modules.
The following laid open Japanese Patent Applications can also be referred to for different techniques addressing similar problems: No. J02/206,939, opened on Aug. 16, 1990 (Okamoto), describes a self-routing distribution network for ATM. It is made up of unit switches and bypass devices. No. J02/170,744, opened on Jul. 2, 1990 (Sumino), teaches ATM digital switching equipment. The equipment has a switch matrix which returns cells to the input buffer when a collision occurs. No. J02/142,240, opened on May 31, 1990 (Uetake at al), describes ATM packet switching equipment. It has buffer memories from which packets are output according to the output priority code obtained from a priority set-up circuit. No. J01/148,000, opened on Jun. 9, 1989 (Abe et al), teaches time-division data switching for a data highway which is operable in ATM and STM.